home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / english / dcodhuff.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  10.0 KB  |  272 lines
  1. /* File: dcodhuff.c
  2.    Author: David Bourgin
  3.    Creation date: 15/2/94
  4.    Last update: 24/7/95
  5.    Purpose: Example of Huffman decoding with a file source to decompress.
  6. */
  7.  
  8. #include <stdio.h>
  9. /* For routines printf,fgetc and fputc */
  10. #include <memory.h>
  11. /* For routine memset */
  12. #include <malloc.h>
  13. /* For routines malloc and free */
  14. #include <stdlib.h>
  15. /* For routine exit */
  16.  
  17. /* Error codes returned to the caller */
  18. #define NO_ERROR      0
  19. #define BAD_FILE_NAME 1
  20. #define BAD_ARGUMENT  2
  21. #define BAD_MEM_ALLOC 3
  22.  
  23. /*  Useful constants */
  24. #define FALSE 0
  25. #define TRUE  1
  26.  
  27. typedef struct s_tree { unsigned int byte;
  28.                              /* A byte has to be coded as an unsigned integer to allow a node to have a value over 255 */
  29.                          struct s_tree *left_ptr,
  30.                                        *right_ptr;
  31.                        } t_tree,*p_tree;
  32. #define TREE_BYTE(ptr_tree)  ((*(ptr_tree)).byte)
  33. #define LEFTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).left_ptr)
  34. #define RIGHTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).right_ptr)
  35.  
  36. typedef struct { unsigned char bits[32];
  37.                  unsigned int bits_nb;
  38.                  unsigned char presence;
  39.                } t_bin_val;
  40. #define BITS_BIN_VAL(x)  ((x).bits)
  41. #define NB_BITS_BIN_VAL(x)  ((x).bits_nb)
  42. #define PRESENCE_BIN_VAL(x)  ((x).presence)
  43.  
  44. /* Global variables */
  45. FILE *source_file,*dest_file;
  46.  
  47.                              /* Being that fgetc=EOF only after an access
  48.                                 then 'byte_stored_status' is 'TRUE' if a byte has been stored by 'fgetc'
  49.                                 or 'FALSE' if there's no valid byte not handled in 'val_byte_stored' */
  50. int byte_stored_status=FALSE;
  51. int byte_stored_val;
  52.  
  53. /* Pseudo procedures */
  54. #define end_of_data()  (byte_stored_status?FALSE:!(byte_stored_status=((byte_stored_val=fgetc(source_file))!=EOF)))
  55. #define read_byte()  (byte_stored_status?byte_stored_status=FALSE,(unsigned char)byte_stored_val:(unsigned char)fgetc(source_file))
  56. #define write_byte(byte)  ((void)fputc((byte),dest_file))
  57.  
  58. unsigned char bit_counter_to_read=0;
  59. unsigned int val_to_read=0;
  60.  
  61. unsigned char read_code_1_bit()
  62. /* Returned parameters: Returns an unsigned integer with the 0-bit (on the right of the integer) valid
  63.    Action: Reads the next bit in the stream of data to compress
  64.    Errors: An input/output error could disturb the running of the program
  65.    The source must have enough bits to read
  66. */
  67. { unsigned int result;
  68.  
  69.   if (bit_counter_to_read)
  70.      { bit_counter_to_read--;
  71.        result=(val_to_read >> bit_counter_to_read) & 1;
  72.      }
  73.   else { val_to_read=read_byte();
  74.          bit_counter_to_read=7;
  75.          result=(val_to_read >> 7) & 1;
  76.        }
  77.   val_to_read &= 127;
  78.   return result;
  79. }
  80.  
  81. unsigned int read_code_n_bits(n)
  82. /* Returned parameters: Returns an unsigned integer with the n-bits (on the right of the integer) valid
  83.    Action: Reads the next n bits in the stream of data to compress
  84.    Errors: An input/output error could disturb the running of the program
  85.    The source must have enough bits to read
  86. */
  87. unsigned char n;
  88. { unsigned int result;
  89.  
  90.   while ((bit_counter_to_read<n)&&(!end_of_data()))
  91.         { val_to_read=(val_to_read << 8)+read_byte();
  92.           bit_counter_to_read += 8;
  93.         }
  94.   bit_counter_to_read -= n;
  95.   result=val_to_read >> bit_counter_to_read;
  96.   val_to_read &= ((1<<bit_counter_to_read)-1);
  97.   return result;
  98. }
  99.  
  100. void read_header(codes_table)
  101. /* Returned parameters: The contain of 'codes_table' is modified
  102.    Action: Rebuilds the binary encoding array by using the header
  103.    Errors: An input/output error could disturb the running of the program
  104. */
  105. t_bin_val codes_table[257];
  106. { register unsigned int i,j;
  107.   char byte_nb;
  108.  
  109.   (void)memset((char *)codes_table,0,257*sizeof(*codes_table));
  110.                              /* == Decoding of the first part of the header === */
  111.   if (read_code_1_bit())
  112.                              /* First bit=0 => Present bytes coded on n*8 bits
  113.                                          =1 => Present bytes coded on 256 bits */
  114.      for (i=0;i<=255;i++)
  115.          PRESENCE_BIN_VAL(codes_table[i])=read_code_1_bit();
  116.   else { i=read_code_n_bits(5)+1;
  117.          while (i)
  118.                { PRESENCE_BIN_VAL(codes_table[read_code_n_bits(8)])=1;
  119.                  i--;
  120.                }
  121.        }
  122.   PRESENCE_BIN_VAL(codes_table[256])=1;
  123.                              /* Presence of a fictive 256-byte is enforced! */
  124.  
  125.                              /* == Decoding the second part of the header == */
  126.   for (i=0;i<=256;i++)
  127.       if PRESENCE_BIN_VAL(codes_table[i])
  128.          { if (read_code_1_bit())
  129.                              /* First bit=0 => 5 bits of binary length-1 followed by a binary word
  130.                                          =1 => 8 bits of binary length-1 followed by a binary word */
  131.               j=read_code_n_bits(8)+1;
  132.            else j=read_code_n_bits(5)+1;
  133.            NB_BITS_BIN_VAL(codes_table[i])=j;
  134.                              /* Reading of a binary word */
  135.            byte_nb=(j+7) >> 3;
  136.            if (j & 7)
  137.               {              /* Reads the bits that takes less than one byte */
  138.                 byte_nb--;
  139.                 BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(j & 7);
  140.               }
  141.            while (byte_nb)
  142.                  {           /* Reads the bits that takes one byte, at least */
  143.                    byte_nb--;
  144.                    BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(8);
  145.                  }
  146.          }
  147. }
  148.  
  149. void suppress_tree(tree)
  150. /* Returned parameters: None
  151.    Action: Suppresses the allocated memory for the tree
  152.    Errors: None if the tree has been build with dynamical allocations!
  153. */
  154. p_tree tree;
  155. { if (tree!=NULL)
  156.      { suppress_tree(LEFTPTR_OF_TREE(tree));
  157.        suppress_tree(RIGHTPTR_OF_TREE(tree));
  158.        free(tree);
  159.      }
  160. }
  161.  
  162. p_tree tree_encoding(codes_table)
  163. /* Returned parameters: A binary tree is returned
  164.    Action: Returns the decoding binary tree built from 'codes_table'
  165.    Errors: None
  166. */
  167. t_bin_val codes_table[257];
  168. { register unsigned int i;
  169.   unsigned int j;
  170.   p_tree ptr_tree,current_node;
  171.  
  172.   if ((ptr_tree=(p_tree)malloc(sizeof(t_tree)))==NULL)
  173.      exit(BAD_MEM_ALLOC);
  174.   TREE_BYTE(ptr_tree)=257;
  175.   LEFTPTR_OF_TREE(ptr_tree)=NULL;
  176.   RIGHTPTR_OF_TREE(ptr_tree)=NULL;
  177.   for (i=0;i<=256;i++)
  178.       { for (current_node=ptr_tree,j=NB_BITS_BIN_VAL(codes_table[i]);j;j--)
  179.           { if (BITS_BIN_VAL(codes_table[i])[(j-1) >> 3] & (1 << ((j-1) & 7)))
  180.                if (LEFTPTR_OF_TREE(current_node)==NULL)
  181.                   { if ((LEFTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL)
  182.                        { suppress_tree(ptr_tree);
  183.                          exit(BAD_MEM_ALLOC);
  184.                        }
  185.                     current_node=LEFTPTR_OF_TREE(current_node);
  186.                     LEFTPTR_OF_TREE(current_node)=NULL;
  187.                     RIGHTPTR_OF_TREE(current_node)=NULL;
  188.                   }
  189.                else current_node=LEFTPTR_OF_TREE(current_node);
  190.             else if (RIGHTPTR_OF_TREE(current_node)==NULL)
  191.                     { if ((RIGHTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL)
  192.                        { suppress_tree(ptr_tree);
  193.                          exit(BAD_MEM_ALLOC);
  194.                        }
  195.                       current_node=RIGHTPTR_OF_TREE(current_node);
  196.                       LEFTPTR_OF_TREE(current_node)=NULL;
  197.                       RIGHTPTR_OF_TREE(current_node)=NULL;
  198.                     }
  199.                  else current_node=RIGHTPTR_OF_TREE(current_node);
  200.             if (j==1)
  201.                TREE_BYTE(current_node)=i;
  202.             else TREE_BYTE(current_node)=257;
  203.           }
  204.       };
  205.   return (ptr_tree);
  206. }
  207.  
  208. void huffmandecoding()
  209. /* Returned parameters: None
  210.    Action: Decompresses with Huffman method all bytes read by the function 'read_code_1_bit' and 'read_code_n_bits'
  211.    Errors: An input/output error could disturb the running of the program
  212. */
  213. { t_bin_val encoding_table[257];
  214.   p_tree ptr_tree,current_node;
  215.  
  216.   if (!end_of_data())    /* Are there data to compress? */
  217.      { read_header(encoding_table);
  218.        ptr_tree=tree_encoding(encoding_table);
  219.        do { current_node=ptr_tree;
  220.             while (TREE_BYTE(current_node)==257)
  221.                   if (read_code_1_bit())
  222.                              /* Bit=1 => Got to left in the node of the tree
  223.                                    =0 => Got to right in the node of the tree */
  224.                      current_node=LEFTPTR_OF_TREE(current_node);
  225.                   else current_node=RIGHTPTR_OF_TREE(current_node);
  226.             if (TREE_BYTE(current_node)<=255)
  227.                write_byte(TREE_BYTE(current_node));
  228.           }
  229.        while (TREE_BYTE(current_node)!=256);
  230.        suppress_tree(ptr_tree);
  231.      }
  232. }
  233.  
  234. void aide()
  235. /* Returned parameters: None
  236.    Action: Displays the help of the program and then stops its running
  237.    Errors: None
  238. */
  239. { printf("This utility enables you to decompress a file by using Huffman method\n");
  240.   printf("as given 'La Video et Les Imprimantes sur PC'\n");
  241.   printf("\nUse: dcodhuff source target\n");
  242.   printf("source: Name of the file to decompress\n");
  243.   printf("target: Name of the restored file\n");
  244. }
  245.  
  246. int main(argc,argv)
  247. /* Returned parameters: Returns an error code (0=None)
  248.    Action: Main procedure
  249.    Errors: Detected, handled and an error code is returned, if any
  250. */
  251. int argc;
  252. char *argv[];
  253. { if (argc!=3)
  254.      { aide();
  255.        exit(BAD_ARGUMENT);
  256.      }
  257.   else if ((source_file=fopen(argv[1],"rb"))==NULL)
  258.           { aide();
  259.             exit(BAD_FILE_NAME);
  260.           }
  261.        else if ((dest_file=fopen(argv[2],"wb"))==NULL)
  262.                { aide();
  263.                  exit(BAD_FILE_NAME);
  264.                }
  265.             else { huffmandecoding();
  266.                    fclose(source_file);
  267.                    fclose(dest_file);
  268.                  }
  269.   printf("Execution of dcodhuff completed.\n");
  270.   return (NO_ERROR);
  271. }
  272.